//给你一个下标从 0 开始、大小为 m x n 的矩阵 grid ，矩阵由若干 正 整数组成。 
//
// 你可以从矩阵第一列中的 任一 单元格出发，按以下方式遍历 grid ： 
//
// 
// 从单元格 (row, col) 可以移动到 (row - 1, col + 1)、(row, col + 1) 和 (row + 1, col + 1) 
//三个单元格中任一满足值 严格 大于当前单元格的单元格。 
// 
//
// 返回你在矩阵中能够 移动 的 最大 次数。 
//
// 
//
// 示例 1： 
// 输入：grid = [[2,4,3,5],[5,4,9,3],[3,4,2,11],[10,9,13,15]]
//输出：3
//解释：可以从单元格 (0, 0) 开始并且按下面的路径移动：
//- (0, 0) -> (0, 1).
//- (0, 1) -> (1, 2).
//- (1, 2) -> (2, 3).
//可以证明这是能够移动的最大次数。 
//
// 示例 2： 
//
// 
//输入：grid = [[3,2,4],[2,1,9],[1,1,7]]
//输出：0
//解释：从第一列的任一单元格开始都无法移动。
// 
//
// 
//
// 提示： 
//
// 
// m == grid.length 
// n == grid[i].length 
// 2 <= m, n <= 1000 
// 4 <= m * n <= 10⁵ 
// 1 <= grid[i][j] <= 10⁶ 
// 
//
// Related Topics 数组 动态规划 矩阵 👍 42 👎 0


package com.tyrone.leetcode.editor.cn;

import com.tyrone.leetcode.util.CodeUtils;

import java.util.Arrays;
import java.util.List;

public class MaximumNumberOfMovesInAGrid {
    public static void main(String[] args) {
        Solution solution = new MaximumNumberOfMovesInAGrid().new Solution();
        String json = "[[65,200,263,220,91,183,2,187,175,61,225,120,39],[111,242,294,31,241,90,145,25,262,214,145,71,294],[152,25,240,69,279,238,222,9,137,277,8,143,143],[189,31,86,250,20,63,188,209,75,22,127,272,110],[122,94,298,25,90,169,68,3,208,274,202,135,275],[205,20,171,90,70,272,280,138,142,151,80,122,130],[284,272,271,269,265,134,185,243,247,50,283,20,232],[266,236,265,234,249,62,98,130,122,226,285,168,204],[231,24,256,101,142,28,268,82,111,63,115,13,144],[277,277,31,144,49,132,28,138,133,29,286,45,93],[163,96,25,9,3,159,148,59,25,81,233,127,12],[127,38,31,209,300,256,15,43,74,64,73,141,200]]";
        int[][] doubleArray = CodeUtils.toDoubleArray(json);
        System.out.println(solution.maxMoves(doubleArray));
        System.out.println(solution.maxMoves(
                new int[][]{
                        {2, 4, 3, 5}, {5, 4, 9, 3}, {3, 4, 2, 11}, {10, 9, 13, 15}
//                        {187,167,209,251,152,236,263,128,135},{267,249,251,285,73,204,70,207,74},{189,159,235,66,84,89,153,111,189},{120,81,210,7,2,231,92,128,218},{193,131,244,293,284,175,226,205,245}
//                        {3,2,4},{2,1,9},{1,1,7}
//                        {1000000,92910,1021,1022,1023,1024,1025,1026,1027,1028,1029,1030,1031,1032,1033,1034,1035,1036,1037,1038,1039,1040,1041,1042,1043,1044,1045,1046,1047,1048,1049,1050,1051,1052,1053,1054,1055,1056,1057,1058,1059,1060,1061,1062,1063,1064,1065,1066,1067,1068},
//                        {1069,1070,1071,1072,1073,1074,1075,1076,1077,1078,1079,1080,1081,1082,1083,1084,1085,1086,1087,1088,1089,1090,1091,1092,1093,1094,1095,1096,1097,1098,1099,1100,1101,1102,1103,1104,1105,1106,1107,1108,1109,1110,1111,1112,1113,1114,1115,1116,1117,1118}
                }));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int maxMoves(int[][] grid) {
            int m = grid.length;
            int n = grid[0].length;
            int[][] dp = new int[m][n];
            for (int i = 0; i < m; i++) {
                Arrays.fill(dp[i], Integer.MIN_VALUE);
            }
            for (int i = 0; i < m; i++) {
                dp[i][0] = 0;
            }
            int[][] dirs = new int[][]{{-1, -1}, {0, -1}, {1, -1}};
            int max = 0;

            for (int j = 1; j < n; j++) {
                for (int i = 0; i < m; i++) {
                    for (int[] dir : dirs) {
                        int x = i + dir[0];
                        int y = j + dir[1];
                        if (0 <= x && x < m && 0 <= y && y < n) {
                            if (grid[i][j] > grid[x][y] && dp[x][y] != Integer.MIN_VALUE) {
                                dp[i][j] = Math.max(dp[i][j], dp[x][y] + 1);
                                max = Math.max(dp[i][j], max);
                            }
                        }
                    }
                }
            }
            return max;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

}